using Utilities.LinkedList;

namespace InsertionSortList
{
    public class Solution
    {
        public ListNode InsertionSortList(ListNode head)
        {
            if (head == null)
            {
                return null;
            }

            var p = head;
            var q = p.next;
            p.next = null;
            while (q != null)
            {
                var temp = q;
                q = q.next;
                var index = this.FindIndex(p, temp);
                if (index == null)
                {
                    temp.next = p;
                    head = temp;
                    p = head;
                }
                else
                {
                    temp.next = index.next;
                    index.next = temp;
                }
            }

            return head;
        }

        private ListNode FindIndex(ListNode head, ListNode q)
        {
            var p = head;

            while (p != null)
            {
                if (p.val < q.val && (p.next == null || p.next.val >= q.val))
                {
                    return p;
                }

                p = p.next;
            }

            return null;
        }
    }
}